package pers.qianyu.month_202012.date_20201220;

import org.junit.*;

import java.util.*;

/**
 * 448. 找到所有数组中消失的数字
 * https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array/
 *
 * @author mizzle rain
 * @date 2020-12-20 15:54
 */
public class FindDisappearedNumbers {
    // 原地标记法
    public List<Integer> findDisappearedNumbers(int[] nums) {
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            int num = nums[i];
            int index = Math.abs(num) - 1;
            if (nums[index] > 0) {
                // 凡是在数组中出现的元素，对应索引出的元素被标记为负数
                nums[index] = -nums[index];
            }
        }
        //System.out.println(Arrays.toString(nums));
        ArrayList<Integer> res = new ArrayList<>();
        for (int i = 1; i <= len; i++) {
            if (nums[i - 1] > 0) {
                res.add(i);
            }
        }
        return res;
    }

    @Test
    public void test1() {
        int[] arr = {4, 3, 2, 7, 8, 2, 3, 1};
        List<Integer> result = new FindDisappearedNumbers().findDisappearedNumbers(arr);
        System.out.println("result = " + result);
    }
}
